package com.wj.sort;

/**
 * 希尔排序
 * @author wen.jie
 * @date 2021/8/5 9:26
 */
public class Shell {

    /**
     * 排序
     * @author wen.jie
     * @date 2021/8/4 17:28
     */
    public static void sort(Comparable<?>[] a) {
        //1.根据数组a的长度确定增长量
        int h = 1;
        while (h < a.length/2) {
            h = 2 * h + 1;
        }
        //2.希尔排序
        while (h >= 1){
            //找到待插入的元素
            for (int i = h; i < a.length; i++) {
                //把待插入的元素插入到有序数列中
                for(int j = i; j >= h; j -= h){
                    if(greater(a[j-h], a[j])){
                        exchange(a, j-h, j);
                    } else break;
                }
            }
            h = h/2;
        }
    }

    /**
     * 比较
     * @author wen.jie
     * @date 2021/8/4 17:18
     */
    private static boolean greater(Comparable v, Comparable w) {
        return v.compareTo(w) > 0;
    }

    /**
     * 交换
     * @author wen.jie
     * @date 2021/8/4 17:27
     */
    private static void exchange(Comparable[] a, int i, int j) {
        Comparable temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }

}
